#include <vector>
#include <string>
#include <bitset>
using namespace std;
class Solution {
private:
    int mapping(const char& c) {
        int res = -1;
        switch (c) {
        case 'A':
            res = 0;
            break;
        case 'C':
            res = 1;
            break;
        case 'G':
            res = 2;
            break;
        case 'T':
            res = 3;
            break;
        }
        return res;
    }
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string>vec;
        if (s.length() < 10)
            return vec;
        bitset<1 << 20> S1;
        bitset<1 << 20> S2;
        int key = 0;
        for (int i = 0; i < 10; ++i) {
            key = key << 2 | mapping(s[i]);
        }
        S1.set(key);
        int mask = (1 << 20) - 1;
        for (int i = 10; i < s.length(); ++i) {
            key = (key << 2 & mask) | mapping(s[i]);
            if (S1[key]) {
                if (!S2[key]) {
                    vec.push_back(s.substr(i - 9, 10));
                    S2.set(key);
                }
            }
            else {
                S1.set(key);
            }
        }
        return vec;
    }
};

int main() {
    Solution sol;
    sol.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
}

//class Solution {
//private:
//    int mapping(const char& c) {
//        int res = -1;
//        switch (c) {
//        case 'A':
//            res = 0;
//            break;
//        case 'C':
//            res = 1;
//            break;
//        case 'G':
//            res = 2;
//            break;
//        case 'T':
//            res = 3;
//            break;
//        }
//        return res;
//    }
//public:
//    vector<string> findRepeatedDnaSequences(string s) {
//        vector<string>vec;
//        if (s.length() < 10)
//            return vec;
//        unordered_map<int, int> map_;
//        int key = 0;
//        for (int i = 0; i < 10 ; ++i) {
//            key = key << 2 | mapping(s[i]);
//        }
//        ++map_[key];
//        for (int i = 10; i < s.length(); ++i) {
//            key <<= 2;
//            key |= mapping(s[i]);
//            key &= 0xfffff;
//            if (map_[key] == 1) {
//                vec.push_back(s.substr(i - 9, 10));
//            }
//            ++map_[key];
//        }
//        return vec;
//
//    }
//};
